package com.lw.leetcode.dp.c;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * c
 * dp
 * 1255. 得分最高的单词集合
 *
 * @author liw
 * @version 1.0
 * @date 2023/1/29 13:06
 */
public class MaxScoreWords {

    private int[] values;
    private int[] items;
    private int[] counts;

    public int maxScoreWords(String[] words, char[] letters, int[] score) {
        int length = words.length;
        this.items = new int[26];
        this.counts = new int[26];
        this.values = new int[length];
        int[][] arr = new int[length][26];
        for (char letter : letters) {
            counts[letter - 'a']++;
        }
        for (int i = 0; i < length; i++) {
            String word = words[i];
            int[] ints = arr[i];
            int l = word.length();
            int s = 0;
            for (int j = 0; j < l; j++) {
                int t = word.charAt(j) - 'a';
                s += score[t];
                ints[t]++;
            }
            values[i] = s;
        }
        int size = 1 << length;
        int max = 0;
        for (int i = 1; i < size; i++) {
            max = Math.max(max, check(arr, i));
        }
        return max;
    }

    private int check(int[][] arr, int v) {
        int index = 0;
        int s = 0;
        Arrays.fill(items, 0);
        while (v != 0) {
            if ((v & 1) == 1) {
                s += values[index];
                int[] ints = arr[index];
                for (int i = 0; i < 26; i++) {
                    items[i] += ints[i];
                }
            }
            v >>= 1;
            index++;
        }
        for (int i = 0; i < 26; i++) {
            if (items[i] > counts[i]) {
                return 0;
            }
        }
        return s;
    }

}
